package com.example.algorithm.backtrcaking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/25
 * n皇后
 */
public class Queen {
    List<List<String>> list=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {

        char [][]chessboard=new char[n][n];
        for(char[]c:chessboard)
        {
            Arrays.fill(c,'.');
        }
        backTarcking(n,0,chessboard);
        return list;
    }

    private void backTarcking(int n, int row, char[][] chessboard) {

        if(n==row)
        {
            list.add(char2List(chessboard));
            return;
        }
        for(int col=0;col<n;col++)
        {
            if(isValid(row,col,n,chessboard))
            {
                chessboard[row][col]='Q';
                backTarcking(n, row+1, chessboard);
                chessboard[row][col]='.';
            }
        }
    }

    private boolean isValid(int row, int col, int n, char[][] chessboard) {

        //判断该列是否存在Q
        for(int i=0;i<row;i++)
        {
            if(chessboard[i][col]=='Q')
            {
                return false;
            }
        }


        //判断左边45度位置是否有Q
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)
        {
            if(chessboard[i][j]=='Q')
            {
                return false;
            }
        }

        //判断右边45度是否有Q
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++)
        {
            if(chessboard[i][j]=='Q')
            {
                return false;
            }
        }
        return true;
    }


    private List char2List(char [][]chessboard)
    {
        List<String> arrayList = new ArrayList<>();
        for(char []c:chessboard)
        {
            arrayList.add(String.copyValueOf(c));
        }
        return arrayList;
    }

    public static void main(String[] args) {
        Queen queen = new Queen();
        List<List<String>> lists = queen.solveNQueens(4);
        lists.stream().forEach(System.out::println);
    }
}
